#include <stdio.h>
#include <stdlib.h>
#include "myLinkList.h"


/*链表的初始化，建立一个空表*/
LINKLIST *init_linklist(){
    LINKLIST *L;
    NODE *temp; 
    L=(LINKLIST *)malloc(sizeof(LINKLIST)); /*动态分配链表的内存空间*/  
    temp=(NODE *)malloc(sizeof(NODE));/*动态分配头结点的内存空间*/
    temp->next=NULL;//头结点的指针域为空 
    L->head=temp;//链表的头结点 
    L->length=0;//链表的长度为0
    return L;
}

/*在链表中的第i个元素之前插入新的元素x，表长加1，并返回1；不成功返回0*/ 
int insert_linklist(LINKLIST *L,int i,datatype x)
{
    NODE *p,*q;//p代表第i个位置前面结点的指针指向，q代表新的结点 
    if(i<1||i>L->length+1)
    {
        printf("插入位置不合法，大于链表的长度\n");
        return 0;
    }
    p=get_linklist(L,i-1);//找到第i个位置前面结点的指针指向
     
    q=(NODE *)malloc(sizeof(NODE));//生成新的结点q 
    q->data=x;//把要插入的值x放入新结点的数据域 
    q->next=p->next;//把p的后继结点放到新结点的指针域 
    p->next=q;//把新结点放到p的指针域 
    L->length++;//链表的长度加1 
    return 1;   
    
}

/*删除链表中的第i个元素，表长减1，并返回1；不成功返回0*/ 
int delete_linklist(LINKLIST *L,int i)
{
    NODE *p,*q;//p代表第i个位置前面结点的指针指向，q代表要删除的结点 
    if(i<1||i>L->length)
    {
        printf("删除位置不合法，大于链表的长度\n");
        return 0;
    }
    p=get_linklist(L,i-1);//找到第i个位置前面结点的指针指向
    
    q=p->next;//临时保存要删除的结点q 
    p->next=q->next;//把要删除的结点的后继结点放到p的指针域
    free(q);//释放要删除的结点q 
    L->length--;//链表的长度减1 
    return 1; 
   
} 

/*返回链表中值为x的元素的序号，若无，返回0 */
int location_linklist(LINKLIST *L,datatype x)
{
    /*
    设个临时结点temp，用于移动，刚开始指向头结点，
    当结点不为空并且该结点的数据域不等于x的时候， temp指向下一个结点，
    并且 还要用个计数器变量，用于统计移动了多少个结点，便于查找成功时候返回序号
    
    只有遍历到最后一个结点，也就是是temp为空的时候，才是查找不成功的时候，返回0 
    */
    NODE *temp=L->head;    
    int count=0;
    do{
        count++;
        temp=temp->next;
    }while(temp!=NULL&&temp->data!=x);
    /*
    while(temp!=NULL&&temp->data!=x)
    {
        count++;
        temp=temp->next;
        
    }
    */
    if(temp==NULL)
        return 0; 
    else
        return count;
     
}

/* 返回链表中第i个元素的结点，若i大于表长，输出提示语 */
NODE *get_linklist(LINKLIST *L,int i)
{
    NODE *temp=L->head;//临时结点，用于移动，最开始指向头结点 
    int j=1;     
    if(i>L->length)
        printf("查找位置%d大于链表的长度%d\n",i,L->length);
    while(j<=i)//当不到查找序号的时候，依次往后移动temp 
    {
        temp=temp->next;
        j++;
    }
    
    return temp;    
} 

//输出链表的元素 
void print_linklist(LINKLIST *L)
{
    NODE *temp;//临时结点，用于移动 
    temp=L->head->next;//指向头结点的后继结点 
    while(temp!=NULL) //循环条件 
    {
        printf("%d  ",temp->data);
        temp=temp->next;//依次往后移动 
    }
    printf("\n");
}
